DISMUTAZIONI
CON RIPETIZIONE DOPPIE
Spigazione di come mi riconduco alla notazione con $|H \cap \sigma H|$ e come modificarla.
A000459.
Vogliamo contare le dismutazioni di {1,1,2,2,3,3,...n,n}:
-
Riordino la stringa: 1,2,3,...n,1,2,3...n.
-
Sto cercando le permutazioni senza i nell'i-esima e nella n±i-esima posizione.
-
Rinomino la seconda metà: n+1,n+2...2n e identifico: $ i \equiv i+n $.
-
O meglio le permutazioni di 1,2,3...2n dove 1 $\equiv$ n+1, 2 $\equiv$ n+2... con lo stesso vincolo di prima.
-
Quindi sto cercando tutte e sole le permutazioni di 1...2n senza punti in comune con 1,2...n,n+1...2n (nessuno al suo posto), né con n+1,n+2...2n,1,2,3...n (nessuno nel n±i posto).
A meno di identificazioni: $/2^n$.
-
Cioè il numero di rettangoli latini $3*2n$ con prime due righe fissate: [1...2n] e [n+1...2n,1...n], fratto $2^n$.
Ossia cerco $\sigma \in S_n$ che applicata alla stringa 1...2n rispetti entrambe le condizioni:
-
$\sigma \circ$1,2,3...2n nessun punto in comune con 1...2n $\rightarrow \sigma \in H_{2n}$ per definizione.
-
$\sigma \circ$1...2n nessun punto in comune con n+1,n+2...2n,1,2,3...n = (1,n+1)(2,n+2)...(n,2n) $\circ$1,2...2n $\rightarrow \sigma \in H_{2n} $(1,n+1)(2,n+2)...(n,2n).
Notazione: stringhe senza parentesi, permutazioni scritte in cicli tra parentesi tonde.
Spiegazione dell'ultima freccia: $\sigma \circ 1,2...n = \sigma \tau ^{-1} (\tau \circ$1,2...n) nessun punto in comune con $\tau \circ$1...n $\rightarrow \sigma \tau ^{-1} \in H_n$ per definizione $\rightarrow \sigma \in H_n \tau$.
Nota: Adesso abbiamo un metodo generale per passare da "non ha punti in comune con XXXX" a $\in H \tau$.
Nota: Il coniugio è una bigezione e preserva la scrittura in cicli, H è definito da questa (tutte e sole le permutazioni di lunghezza massima), quindi H è invariante per coniugio.
$\sigma H \sigma^{-1} = H \rightarrow \ H \sigma = (\sigma H \sigma^{-1}) \sigma = \sigma H$.
Così possiamo concludere che il numero di dismutazioni di {1,1,2,2,3,3...n,n} è:
$$ \frac{|H_{2n} \cap (1,n+1)(2,n+2)(3,n+3)...(n,2n)H_{2n}|}{2^n}$$
Aldilà della riformulazione, per risolvere il problema mi riconduco alla tecnica "dell'hotel" (Vedi prima spiegazione per rettangoli latini) e con il principio di inclusione-esclusione ottengo:
$$ \frac{1}{2^n}* \sum_{i+2j+k=2n} (-1)^{2n-i}* \binom{n}{j} * \binom{n-j}{k}*2^k *i^{2j}*(i-1)^{2k}*(i-2)^{(i-k)}$$
Per più dettagli: [email protected]
Codice python per verificare:
import math
def dism2(n):
if n==0: return 1
s=0
for h in range (0,2*n+1):
for j in range (0, h+1):
if h-2*j>=0 and n>=h-j:
k=h-2*j
i=2*n-h
a=math.comb(n,j)*math.comb(n-j,k)*pow(2,k)*pow(i,2*j)*pow(i-1,2*k)*pow(i-2,i-k)*pow(-1,k%2)
s+=a
return s/pow(2,n)
for n in range (0,11):
print(dism2(n))
#coincide con OEIS :)
Nota: anche altre scritture in bicicli erano equivalenti, si tratta solo di rinominare (o di identificare diversamente all'inizio), inoltre posso spezzare in più bicicli:
$|H_{2n} \cap (1,n+1)(2,n+2)(3,n+3)...(n,2n)H_{2n}| =
|H_{2n} \cap (1,2)(3,4)(5,6)...(2n-1,2n)H_{2n}| =
|H_{2n} \cap (1,2)H_{2n} \cap (3,4)H_{2n} \cap ...(2n-1,2n)H_{2n}|$.
L'unica cosa che conta è che i vincoli siano gli stessi, ad esempio: niente punti in comune con "12345, 31254 e 23145" è uguale a niente punti in comune con "12345, 21345, 32145, 13245 e 12345", si vede chiaramente impilando le righe che ogni colonna ha tutti e soli gli stessi vincoli. Passando alla notazione con le dismutazioni:
$|H \cap (123)(45)H \cap (132)H| = |H \cap (12)H \cap (13)H \cap (23)H \cap (45)H|.$
Abbiamo un metodo per riscrivere alcune intersezioni tra H e i suoi traslati.
Ad esempio due permutazioni disgiunte ($\sigma$, $\tau$) sono sempre "unibili", come nel caso sopra dei bicicli:
$|H \cap \sigma \tau H|$ = $|H \cap \sigma H \cap \tau H|.$
Nota: questo approccio è generalizzabile a dismutazioni con ripetizioni generiche: {1,1...1,2,2...2,3...3...n...n}.
Chiamiamo $k_i$ il numero di volte che compaiono numeri <=i, allora i sarà presente $k_i-k_{i-1}$ volte.
Adesso possiamo procedere come prima rinominando tutto in ordine e identificando 1,2...$k_1$ tra loro, poi $k_1$+1...$k_2$ etc.
Cerchiamo permutazioni {1,2...$k_n$} con il vincolo che 1,2...$k_1$ non siano nei primi $k_1$ posti, $k_1$+1...$k_2$ non siano nei $k_1$+1...$k_2$ posti e così via. A meno di identificazione.
Il primo vincolo è rappresenzatibili da "nessun punto in comune con" un insieme di stringhe che hanno ogni elemento 1-$k_1$ in ogni posizione tra 1-$k_1$ (e fissano il resto)
($\star$)
, ad esempio (1,2...$k_1$) e le sue potenze - applicate a 1...$k_n$.
In base a questa scelta otteniamo identità come prima, ad esempio potevo prendere tutti i bicicli contenenti 1-$k_1$.
Analogamente imponiamo i vincoli per il resto della stringa e possiamo passare alla notazione con le dismutazioni:
$$ \frac{1}{k_1!*(k_2-k_1)!*...*(k_n-k_{n-1})!} |\bigcap_{i=1}^{k_1} (1,2...k_1)^iH \ \cap \ \bigcap_{i=1}^{k_2-k_1} (k_1+1...k_2)^iH \ \cap... \bigcap_{i=1}^{k_n-k_{n-1}} (k_{n-1}+1...k_n)^iH|.$$
Ad esempio dism. di {1111223} le vedo come permutazioni di 1...7 senza punti in comune con "1234567, 4123567, 3412567, 2341567 e 1234657" cioè:
$$\frac{1}{4!*2!}*|\bigcap_{i=0}^3 (1,2,3,4)^iH \ \cap \ (5,6)H|.$$
Ora uniamo i vincoli (come prima) e chiamiamo m:= max {$k_i-k_{i-1}$}, possiamo concludere che il numero cercato è:
$$\frac{1}{k_1!*(k_2-k_1)!*...*(k_n-k_{n-1})!}*|\bigcap_{i=1}^{m} (1,2...k_1)^i \circ (k_1+1...k_2)^i \circ ... (k_{n-1}+1...k_n)^iH|$$
Continuando l'esempio: sto unendo i vincoli in "412365, 341256, 234165 e 123456", cioè:
$$\frac{1}{4!*2!}*|\bigcap_{i=1}^4 (1,2,3,4)^i(5,6)^iH|.$$
$\star$: può essere interessante chiedersi quali sottoinsiemi di $S_k$ godano di questa proprietà, cioè che applicati a 1...k mandino ogni elemento in ogni posizione.
Ad esempio un k-ciclo e le sue potenze oppure tutti i bicicli.
Perchè sono tutti i modi di riscrivere qualcosa che mi rappresenta dismutazioni con ripetizione (da approfondire).
Jack Boncompagni.